Systems that operate on sensitive data need to protect against unauthorized access to, or disclosure or alteration of, such data. Digital signatures can be used to attest to the integrity and authenticity of sensitive data. Tamper resistant cryptographic devices used to sign sensitive data may be used in environments where attackers can gain physical access to the device. Attackers who gain access to cryptographic keys and other secrets could generate counterfeit data, forge signatures or steal or otherwise tamper with the sensitive data, leading to severe consequences such as the subversion of critical operations of the system and exposure of confidential or proprietary information or expose unintended access to a physical resource.
In a “fault attack,” an attacker deliberately attempts to modify some aspect of a device or its environment in the hopes of introducing an error or fault (“glitch”) into an operation and gaining access to secret keys. Some non-transient fault attacks use a focused ion beam station to physically modify a device circuit. Transient faults are not intended to permanently modify the target device. Some of the best known transient fault injection techniques include introducing variations into a supply voltage, clock frequency, temperature, or blasting a circuit with a laser or other pulse of light.
Faults can have many effects. They can cause a step in a computation to be skipped. They can cause a step to be repeated. They can cause one operation to be substituted for another. They can modify a value in a memory or traversing a bus—for example, changing the address from which data or instructions are loaded. They can cause a value to be zeroed, or set to some other value. Such faults can lead to a cryptographic operation mixing a partially correct result with a partially corrupted state. Many faults are exploited by analyzing partially corrupted states.
Another type of attack depends on a transient fault that disrupts one type of computation but has no impact on another. For example, a certain physical glitch might kill operations of type “A”, but have no impact if triggered during an operation of type “B”. Observing which time locations are “safe”, i.e. do not affect the result of the computation, allows an attacker to infer locations of the operations “B” which may in turn compromise the security.
Many countermeasures for preventing fault attacks have been developed. Some approaches are based on adding additional circuits to detect faults. Other approaches randomize the clock to make landing precisely-timed glitches harder. Duplicate circuits can perform a calculation twice; a fault in one circuit that leads to a difference in result may be detected. Software techniques involve performing additional verification steps, or implementing cryptographic algorithms to resist or detect faults. For example, one early countermeasure involved simply performing the calculation twice (perhaps using two different implementations) and confirming that the results are the same. Another approach is to perform a calculation such as decryption and then a corresponding inverse operation such as encryption and confirm that the output of the inverse operation is equal to the initial input before further processing the decryption result. Signature systems (including DSA) can check the signature result by performing a public key verification. This is particularly efficient for RSA, where checking the signature is much faster than calculating it (in contrast to DSA, where the public key verification is much slower than signing). This public key verification step confirms that the signature does indeed correspond to the message (or message hash) being signed. Notwithstanding, in a DSA system the public key verification step does nothing to prove that the nonce has not been reused or that it has not otherwise been tampered with.
Many countermeasures specific to RSA-CRT have been proposed, including some that expand some of the moduli used in the calculations in a way that allows a quick “sanity check” to be implemented using a few extra reductions. Still others attempt to implement cryptographic algorithms in a “fail safe” manner—i.e. where a faulty output is not helpful in recovering the secret key.
However, digital signature systems based on the discrete log problem (such as, for example ElGamal Signature Algorithm, Digital Signature Algorithm (DSA), and the elliptic-curve counterparts) are based on significantly different principles than RSA-CRT, and are subject to additional glitch attacks. For example, DSA signature systems use a random unique value (nonce) to secure each signature. The security of DSA requires that these nonce values remain secret, and never be reused. An attacker who collects n signatures can use them to construct n equations in (n+1) unknowns. If a nonce is reused or if a nonce's value becomes known then the system of n equations has only n unknowns, and the attacker can use standard algebraic methods to solve for the private key, d, also called the signing key. Fault attacks against devices employing these algorithms can succeed by introducing a “fault” or “glitch” in the operation of the device that causes a nonce value to be reused. Other fault or glitch attacks may cause a nonce to be forced to a known value, or an unknown value that is used multiple times. Still other fault or glitch attacks may cause one of the operations to be skipped during the modular exponentiation (or curve multiplication). Other faults may cause a multiplication or reduction not to take place in a later stage of the computation.
Because nonce values need to be unique for each message, confirming that a DSA signature corresponds to the message (hash) being signed does not prove that no compromising fault has taken place.